package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import org.junit.Test;

/**
*作者：furong
*日期：2017年3月6日
*时间：下午4:56:41
*/
public class Q176 {
    class DirectedGraphNode {
        int label;
        ArrayList<DirectedGraphNode> neighbors;

        DirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }

    /**
     * @param graph: A list of Directed graph node
     * @param s: the starting Directed graph node
     * @param t: the terminal Directed graph node
     * @return: a boolean value
     */
    boolean hasRout = false;

    public boolean hasRoute(ArrayList<DirectedGraphNode> graph, DirectedGraphNode s, DirectedGraphNode t) {
        if (s == null || t == null || graph == null || graph.size() <= 2 || !graph.contains(s) || !graph.contains(t)) {
            return hasRout;
        }
        Set<DirectedGraphNode> exclude = new HashSet<>();
        search(s, t, exclude);
        return hasRout;
    }

    private void search(DirectedGraphNode s, DirectedGraphNode t, Set<DirectedGraphNode> exclude) {
        if (!hasRout) {
            if (s.equals(t)) {
                hasRout = true;
                return;
            }
            if (s.neighbors != null) {
                for (DirectedGraphNode node : s.neighbors) {
                    if (exclude.contains(node)) {
                        continue;
                    } else {
                        exclude.add(node);
                        search(node, t, exclude);
                    }
                }
            }
        }
    }

    @Test
    public void testA() {
        DirectedGraphNode d0 = new DirectedGraphNode(0);
        DirectedGraphNode d1 = new DirectedGraphNode(1);
        DirectedGraphNode d2 = new DirectedGraphNode(2);
        DirectedGraphNode d3 = new DirectedGraphNode(3);
        DirectedGraphNode d4 = new DirectedGraphNode(4);
        DirectedGraphNode d5 = new DirectedGraphNode(5);
        DirectedGraphNode d6 = new DirectedGraphNode(6);
        DirectedGraphNode d7 = new DirectedGraphNode(7);
        DirectedGraphNode d8 = new DirectedGraphNode(8);
        DirectedGraphNode d9 = new DirectedGraphNode(9);
        d0.neighbors = (ArrayList<DirectedGraphNode>) Arrays.asList(d1, d4, d5, d7, d8, d9);
        d1.neighbors = (ArrayList<DirectedGraphNode>) Arrays.asList(d3, d4);
        d2.neighbors = (ArrayList<DirectedGraphNode>) Arrays.asList(d8, d3, d4, d5, d7);
        d3.neighbors = (ArrayList<DirectedGraphNode>) Arrays.asList(d6);
        d4.neighbors = (ArrayList<DirectedGraphNode>) Arrays.asList(d4, d6);
        d5.neighbors = (ArrayList<DirectedGraphNode>) Arrays.asList(d1, d3, d4, d6, d9);
        d7.neighbors = (ArrayList<DirectedGraphNode>) Arrays.asList(d9, d3, d4, d5, d1);
        d8.neighbors = (ArrayList<DirectedGraphNode>) Arrays.asList(d9, d3, d4, d6);
        d9.neighbors = (ArrayList<DirectedGraphNode>) Arrays.asList(d3, d4, d6);

    }
}
